home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / Libraries / StdSet 1.0 / StdSet.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-07-20  |  12.2 KB  |  502 lines  |  [TEXT/MPS ]
  1.  
  2. #include "StdSet.h"
  3. #include <Types.h>
  4. #include <Memory.h>
  5. #include <ToolUtils.h>
  6. #include <OSUtils.h>
  7. #include <StdDef.h>
  8. #include <StdLib.h>
  9. #include <String.h>
  10. #include <Errors.h>
  11.  
  12. /* File StdSet.c
  13.     operations for sets of long integers or pointers, implementation.
  14.     Copyright (c) 1996, 1997 by John Montbriand.  All Rights Reserved.
  15.     Permission hereby granted for public use.
  16.         Distribute freely in areas where the laws of copyright apply.
  17.     USE AT YOUR OWN RISK.
  18.     DO NOT DISTRIBUTE MODIFIED COPIES.
  19.     Comments/questions/postcards* to the author at the address:
  20.       John Montbriand
  21.       P.O. Box. 1133
  22.       Saskatoon Saskatchewan Canada
  23.       S7K 3N2
  24.     or by email at:
  25.       tinyjohn@sk.sympatico.ca
  26.     *if you mail a postcard, then I will provide you with technical support
  27.     regarding questions you may have about this file.
  28.           see also: <http://www3.sk.sympatico.ca/tinyjohn>
  29. */
  30.                      
  31.  
  32. #define kSetBufSz 64
  33.  
  34. static Boolean rSetSearch(TSETELT* list, TSETELT key, long first, long last, long* where) {
  35.     if (last < first) {
  36.         *where = first;
  37.         return false;
  38.     } else {
  39.         long mid = (first + last) / 2;
  40.         TSETELT midval = list[mid];
  41.         if (key == midval) {
  42.             *where = mid;
  43.             return true;
  44.         } else if (key > midval)
  45.             return rSetSearch(list, key, mid + 1, last, where);
  46.         else return rSetSearch(list, key, first, mid - 1, where);
  47.     }
  48. }
  49.  
  50. static Boolean SetSearch(SetHandle set, TSETELT key, long* where) {
  51.     return rSetSearch((*set)->elt, key, 0, (*set)->n - 1, where);
  52. }
  53.  
  54. SetHandle NewSet(void) {
  55.     return (SetHandle) NewHandleClear(offsetof(SetRecord, elt));
  56. }
  57.  
  58. void ClearSet(SetHandle set) {
  59.     SetHandleSize((Handle) set, offsetof(SetRecord, elt));
  60.     (**set).n = 0;
  61. }
  62.  
  63.  
  64. static int SetEltCompare(const void *a, const void *b) {
  65.     return (* (TSETELT*) a) - (* (TSETELT*) b);
  66. }
  67.  
  68. SetHandle BuildSet(long count, TSETELT *data) {
  69.     SetHandle set;
  70.     TSETELT *srcp;
  71.     long i;
  72.     if ((set = NewSet()) == NULL) return NULL;
  73.     for (srcp = data, i=0; i<count; i++)
  74.         if (!SetAddElt(set, *srcp++)) {
  75.             DisposeSet(set);
  76.             return NULL;
  77.         }
  78.     return set;
  79. }
  80.  
  81. void DisposeSet(SetHandle set) {
  82.     DisposeHandle((Handle) set);
  83. }
  84.  
  85. Boolean SetCopy(SetHandle dst, SetHandle src) {
  86.     long bytes;
  87.     bytes = GetHandleSize((Handle) src);
  88.     SetHandleSize((Handle) dst, bytes);
  89.     if (MemError() != noErr) return false;
  90.     BlockMoveData(*src, *dst, bytes);
  91.     return true;
  92. }
  93.  
  94. Boolean SetAddElt(SetHandle set, TSETELT value) {
  95.     long where, i;
  96.     SetRecord *sp;
  97.     if (SetSearch(set, value, &where)) return true;
  98.     SetHandleSize((Handle) set, offsetof(SetRecord, elt) + ((*set)->n + 1)*sizeof(TSETELT));
  99.     if (MemError() != noErr) return false;
  100.     sp = *set;
  101.     sp->n += 1;
  102.     for (i = sp->n - 1; i > where; i--) sp->elt[i] = sp->elt[i-1];
  103.     sp->elt[where] = value;
  104.     return true;
  105. }
  106.  
  107. void SetRemoveElt(SetHandle set, TSETELT value) {
  108.     long where;
  109.     if (SetSearch(set, value, &where)) {
  110.         Munger((Handle) set,
  111.             offsetof(SetRecord, elt) + where*sizeof(TSETELT),
  112.                 NULL, sizeof(TSETELT), &value, 0);
  113.         (*set)->n -= 1;
  114.     }
  115. }
  116.  
  117. Boolean SetEmpty(SetHandle a) {
  118.     return ((*a)->n == 0);
  119. }
  120.  
  121. Boolean SetEqual(SetHandle a, SetHandle b) {
  122.     TSETELT *vala, *valb, *enda, *endb;
  123.     enda = (vala = (*a)->elt) + (*a)->n;
  124.     endb = (valb = (*b)->elt) + (*b)->n;
  125.     while (vala < enda && valb < endb)
  126.         if (*vala++ != *valb++) return false;
  127.     return (vala == enda && valb == endb);
  128. }
  129.  
  130. Boolean SetSubset(SetHandle a, SetHandle b) {
  131.     TSETELT *vala, *valb, *enda, *endb;
  132.     enda = (vala = (*a)->elt) + (*a)->n;
  133.     endb = (valb = (*b)->elt) + (*b)->n;
  134.     while (vala < enda && valb < endb) {
  135.         if (*vala == *valb) {
  136.             vala++;
  137.             valb++;
  138.         } else if (*vala < *valb)
  139.             vala++;
  140.         else return false;
  141.     }
  142.     if ((*a)->n == 0)
  143.         return ((*b)->n == 0); // empty set is subset of empty set
  144.     else return true;
  145. }
  146.  
  147. Boolean SetMember(SetHandle a, TSETELT value) {
  148.     long where;
  149.     return SetSearch(a, value, &where);
  150. }
  151.  
  152. SetHandle SetAnd(SetHandle a, SetHandle b) {
  153.     TSETELT *vala, *valb, *enda, *endb;
  154.     SetHandle c;
  155.     TSETELT bufferp[kSetBufSz], *putp;
  156.     long count;
  157.     OSErr err;
  158.     putp = bufferp;
  159.     if ((c = NewSet()) == NULL) return NULL;
  160.     HLock((Handle) a);
  161.     HLock((Handle) b);
  162.     enda = (vala = (*a)->elt) + (*a)->n;
  163.     endb = (valb = (*b)->elt) + (*b)->n;
  164.     while (vala < enda && valb < endb) {
  165.         if (*vala == *valb) {
  166.             if (putp - bufferp == kSetBufSz) {
  167.                 err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  168.                 if (err != noErr) goto bail;
  169.                 (*c)->n += kSetBufSz;
  170.                 putp = bufferp;
  171.             }
  172.             *putp++ = *vala++;
  173.             valb++;
  174.         } else if (*vala < *valb) vala++; else valb++;
  175.     }
  176.     if ((count = putp - bufferp) > 0) {
  177.         err = PtrAndHand(bufferp, (Handle) c, count*sizeof(TSETELT));
  178.         if (err != noErr) goto bail;
  179.         (*c)->n += count;
  180.     }
  181.     HUnlock((Handle) a);
  182.     HUnlock((Handle) b);
  183.     return c;
  184. bail:
  185.     HUnlock((Handle) a);
  186.     HUnlock((Handle) b);
  187.     DisposeHandle((Handle) c);
  188.     return NULL;
  189. }
  190.  
  191. SetHandle SetOr(SetHandle a, SetHandle b) {
  192.     TSETELT *vala, *valb, *enda, *endb;
  193.     SetHandle c;
  194.     TSETELT bufferp[kSetBufSz], *putp;
  195.     long count;
  196.     OSErr err;
  197.     putp = bufferp;
  198.     if ((c = NewSet()) == NULL) return NULL;
  199.     HLock((Handle) a);
  200.     HLock((Handle) b);
  201.     enda = (vala = (*a)->elt) + (*a)->n;
  202.     endb = (valb = (*b)->elt) + (*b)->n;
  203.     while (vala < enda && valb < endb) {
  204.         if (*vala == *valb) {
  205.             if (putp - bufferp == kSetBufSz) {
  206.                 err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  207.                 if (err != noErr) goto bail;
  208.                 (*c)->n += kSetBufSz;
  209.                 putp = bufferp;
  210.             }
  211.             *putp++ = *vala++;
  212.             valb++;
  213.         } else if (*vala < *valb) {
  214.             if (putp - bufferp == kSetBufSz) {
  215.                 err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  216.                 if (err != noErr) goto bail;
  217.                 (*c)->n += kSetBufSz;
  218.                 putp = bufferp;
  219.             }
  220.             *putp++ = *vala++;
  221.         } else {
  222.             if (putp - bufferp == kSetBufSz) {
  223.                 err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  224.                 if (err != noErr) goto bail;
  225.                 (*c)->n += kSetBufSz;
  226.                 putp = bufferp;
  227.             }
  228.             *putp++ = *valb++;
  229.         }
  230.     }
  231.     while (vala < enda) {
  232.         if (putp - bufferp == kSetBufSz) {
  233.             err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  234.             if (err != noErr) goto bail;
  235.             (*c)->n += kSetBufSz;
  236.             putp = bufferp;
  237.         }
  238.         *putp++ = *vala++;
  239.     }
  240.     while (valb < endb) {
  241.         if (putp - bufferp == kSetBufSz) {
  242.             err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  243.             if (err != noErr) goto bail;
  244.             (*c)->n += kSetBufSz;
  245.             putp = bufferp;
  246.         }
  247.         *putp++ = *valb++;
  248.     }
  249.     if ((count = putp - bufferp) > 0) {
  250.         err = PtrAndHand(bufferp, (Handle) c, count*sizeof(TSETELT));
  251.         if (err != noErr) goto bail;
  252.         (*c)->n += count;
  253.     }
  254.     HUnlock((Handle) a);
  255.     HUnlock((Handle) b);
  256.     return c;
  257. bail:
  258.     HUnlock((Handle) a);
  259.     HUnlock((Handle) b);
  260.     DisposeHandle((Handle) c);
  261.     return NULL;
  262. }
  263.  
  264. SetHandle SetXor(SetHandle a, SetHandle b) {
  265.     TSETELT *vala, *valb, *enda, *endb;
  266.     SetHandle c;
  267.     TSETELT bufferp[kSetBufSz], *putp;
  268.     long count;
  269.     OSErr err;
  270.     putp = bufferp;
  271.     if ((c = NewSet()) == NULL) return NULL;
  272.     HLock((Handle) a);
  273.     HLock((Handle) b);
  274.     enda = (vala = (*a)->elt) + (*a)->n;
  275.     endb = (valb = (*b)->elt) + (*b)->n;
  276.     while (vala < enda && valb < endb) {
  277.         if (*vala == *valb) {
  278.             vala++;
  279.             valb++;
  280.         } else if (*vala < *valb) {
  281.             if (putp - bufferp == kSetBufSz) {
  282.                 err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  283.                 if (err != noErr) goto bail;
  284.                 (*c)->n += kSetBufSz;
  285.                 putp = bufferp;
  286.             }
  287.             *putp++ = *vala++;
  288.         } else {
  289.             if (putp - bufferp == kSetBufSz) {
  290.                 err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  291.                 if (err != noErr) goto bail;
  292.                 (*c)->n += kSetBufSz;
  293.                 putp = bufferp;
  294.             }
  295.             *putp++ = *valb++;
  296.         }
  297.     }
  298.     while (vala < enda) {
  299.         if (putp - bufferp == kSetBufSz) {
  300.             err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  301.             if (err != noErr) goto bail;
  302.             (*c)->n += kSetBufSz;
  303.             putp = bufferp;
  304.         }
  305.         *putp++ = *vala++;
  306.     }
  307.     while (valb < endb) {
  308.         if (putp - bufferp == kSetBufSz) {
  309.             err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  310.             if (err != noErr) goto bail;
  311.             (*c)->n += kSetBufSz;
  312.             putp = bufferp;
  313.         }
  314.         *putp++ = *valb++;
  315.     }
  316.     if ((count = putp - bufferp) > 0) {
  317.         err = PtrAndHand(bufferp, (Handle) c, count*sizeof(TSETELT));
  318.         if (err != noErr) goto bail;
  319.         (*c)->n += count;
  320.     }
  321.     HUnlock((Handle) a);
  322.     HUnlock((Handle) b);
  323.     return c;
  324. bail:
  325.     HUnlock((Handle) a);
  326.     HUnlock((Handle) b);
  327.     DisposeHandle((Handle) c);
  328.     return NULL;
  329. }
  330.  
  331. SetHandle SetRemove(SetHandle a, SetHandle b) {
  332.     TSETELT *vala, *valb, *enda, *endb;
  333.     SetHandle c;
  334.     TSETELT bufferp[kSetBufSz], *putp;
  335.     long count;
  336.     OSErr err;
  337.     putp = bufferp;
  338.     if ((c = NewSet()) == NULL) return NULL;
  339.     HLock((Handle) a);
  340.     HLock((Handle) b);
  341.     enda = (vala = (*a)->elt) + (*a)->n;
  342.     endb = (valb = (*b)->elt) + (*b)->n;
  343.     while (vala < enda && valb < endb) {
  344.         if (*vala == *valb) {
  345.             vala++;
  346.             valb++;
  347.         } else if (*vala < *valb) {
  348.             if (putp - bufferp == kSetBufSz) {
  349.                 err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  350.                 if (err != noErr) goto bail;
  351.                 (*c)->n += kSetBufSz;
  352.                 putp = bufferp;
  353.             }
  354.             *putp++ = *vala++;
  355.         } else valb++;
  356.     }
  357.     while (vala < enda) {
  358.         if (putp - bufferp == kSetBufSz) {
  359.             err = PtrAndHand(bufferp, (Handle) c, kSetBufSz*sizeof(TSETELT));
  360.             if (err != noErr) goto bail;
  361.             (*c)->n += kSetBufSz;
  362.             putp = bufferp;
  363.         }
  364.         *putp++ = *vala++;
  365.     }
  366.     if ((count = putp - bufferp) > 0) {
  367.         err = PtrAndHand(bufferp, (Handle) c, count*sizeof(TSETELT));
  368.         if (err != noErr) goto bail;
  369.         (*c)->n += count;
  370.     }
  371.     HUnlock((Handle) a);
  372.     HUnlock((Handle) b);
  373.     return c;
  374. bail:
  375.     HUnlock((Handle) a);
  376.     HUnlock((Handle) b);
  377.     DisposeHandle((Handle) c);
  378.     return NULL;
  379. }
  380.  
  381.  
  382. long SetCard(SetHandle a) {
  383.     return (*a)->n;
  384. }
  385.  
  386. TSETELT SetElement(SetHandle a, long index) {
  387.     return (*a)->elt[index];
  388. }
  389.  
  390. static int SetCompareCard(const void *a, const void *b) {
  391.     long carda, cardb, i;
  392.     SetHandle lsa, lsb;
  393.     TSETELT elta, eltb;
  394.         /* check for NULL sets */
  395.     if (a == NULL && b == NULL)
  396.         return 0;
  397.     else if (a == NULL && b != NULL)
  398.         return -1;
  399.     else if (a != NULL && b == NULL)
  400.         return 1;
  401.         /* compare the sets */
  402.     lsa =  * (SetHandle*) a;
  403.     lsb =  * (SetHandle*) b;
  404.     carda = SetCard(lsa);
  405.     cardb = SetCard(lsb);
  406.     if (carda == cardb && carda > 0) {
  407.         for (i=0; i<carda;i++) {
  408.             elta = SetElement(lsa, i);
  409.             eltb = SetElement(lsb, i);
  410.             if (elta != eltb) return (elta - eltb);
  411.         }
  412.         return 0;
  413.     } else return carda - cardb;
  414. }
  415. typedef Boolean (*PowerSetFilter)(SetHandle a);
  416.  
  417. PowerSet GeneratePowerSet(SetHandle a) {
  418.     long n, i, j, next, count;
  419.     TSETELT item;
  420.     PowerSet powerset;
  421.     SetHandle *psp;
  422.     if ((*a)->n > 24) return NULL;
  423.     n = 1;
  424.     count = 1 << (*a)->n;
  425.     powerset = (PowerSet) NewHandleClear(count * sizeof(long));
  426.     if (powerset == NULL) return NULL;
  427.     HLock((Handle) powerset);
  428.     psp = *powerset;
  429.     for (i=0; i < count; i++) 
  430.         if ((psp[i] = NewSet()) == NULL) goto bail;
  431.     for (i=0; i < (*a)->n; i++) {
  432.         item = SetElement(a, i);
  433.         for (j=0, next=n; j< n; j++, next++) {
  434.             SetCopy(psp[next], psp[j]);
  435.             if (!SetAddElt(psp[next], item)) goto bail;
  436.         }
  437.         n = next;
  438.     }
  439.     qsort(psp, count, sizeof(SetHandle), SetCompareCard);
  440.     HUnlock((Handle) powerset);
  441.     return powerset;
  442. bail:
  443.     if (powerset != NULL) {
  444.         for (i=0; i < count; i++) if (psp[i] != NULL)
  445.             DisposeSet(psp[i]);
  446.         DisposeHandle((Handle) powerset);
  447.     }
  448.     return NULL;
  449. }
  450.  
  451. void DisposePowerSet(PowerSet powerset) {
  452.     SetHandle *psp;
  453.     long i, count;
  454.     count = GetHandleSize((Handle) powerset) / sizeof(SetHandle);
  455.     HLock((Handle) powerset);
  456.     psp = *powerset;
  457.     for (i=0; i < count; i++) if (psp[i] != NULL)
  458.         DisposeSet(psp[i]);
  459.     DisposeHandle((Handle) powerset);
  460. }
  461.  
  462. SetHandle PowerSetElt(PowerSet powerset, long index) {
  463.     return (*powerset)[index];
  464. }
  465.  
  466. long PowerSetSize(PowerSet powerset) {
  467.     return GetHandleSize((Handle) powerset) / sizeof(SetHandle);
  468. }
  469.  
  470.  
  471. static Boolean rSetPermute(TSETELT* elts, long nelts, long rotcount, SetPermutation perm, long param) {
  472.     if (rotcount == 1)
  473.         return perm(elts, nelts, param);
  474.     else {
  475.         long i;
  476.         for (i=0; i<rotcount; i++) {
  477.             TSETELT savelast;
  478.             if (!rSetPermute(elts, nelts, rotcount-1, perm, param)) return false;
  479.             savelast = elts[rotcount-1];
  480.             memmove(elts+1, elts, (rotcount-1)*sizeof(TSETELT));
  481.             elts[0] = savelast;
  482.         }
  483.         return true;
  484.     }
  485. }
  486.  
  487. OSErr SetPermute(SetHandle a, SetPermutation perm, long param) {
  488.     long n, i;
  489.     OSErr err;
  490.     TSETELT *locallist;
  491.     locallist = NULL;
  492.     if ((n = SetCard(a)) == 0) return paramErr;
  493.     locallist = (TSETELT *) NewPtr(sizeof(TSETELT) * n);
  494.     if ((err = MemError()) != noErr) return err;
  495.     for (i=0; i<n; i++) locallist[i] = (**a).elt[i];
  496.     rSetPermute(locallist, n, n, perm, param);
  497.     DisposePtr((Ptr) locallist);
  498.     return noErr;
  499. }
  500.  
  501.  
  502.